import { checkArr } from "./util"

/**
 * 归并排序
 * @param arr 
 */
export const mergeSort = (arr: number[]) => {
    if (checkArr(arr)) return

    // 获取长度
    let len = arr.length;


    /**
     * tar替换ori的位置的值
     * @param ori 
     * @param tar 
     */
    const replace = (ori: number, tar: number) => arr[ori] = tar

    /**
     * 合并数组
     * @param s 
     * @param m 
     * @param e 
     */
    const merge = (s: number, m: number, e: number) => {
        // 1. 拷贝左边的数组
        // debugger
        const leftArr = arr.slice(s, m);
        /**
         * 比较数组中两个所以对应的值的大小
         * @param l 
         * @param r 
         */
        const compare = (l: number, r: number) => leftArr[l] - arr[r];


        // 2. 确定 ai([s, e) 数组的开始下标), li (拷贝的leftArr开始下标), ri(右边数组的开始下标), le(左边数组的结束下标), re (右边数组的结束下标) 
        let ai = s, 
            li = 0, 
            ri = m, 
            le = m - s, 
            re = e;
            // ai == li == 0
            // ri = 6, le = 1 re = 7

        // 3. 左边和右边开始比较
        // 左边先结束  li === le
        // 右边先结束  ri === re
        while (li < le && ri < re) {
            if (compare(li, ri) > 0) { // l > r
                // 使用ri替代ai的位置
                replace(ai, arr[ri]);
                ri++
            } else { // r >= l
                // 使用li替代ai
                replace(ai, leftArr[li])
                li++;
            }
            // ai都要++
            ai++
        }
        
        // 4. 处理左右结束时数组处理

        // 右边先结束 （左边先结束不用处理）
        if (ri === re) {
            // 将leftArr全部转移到数组中去
            for (let i = li; i < le; i++) {
                arr[ai++] = leftArr[i]
            }
        }
    }

    /**
     * 分割
     * @param s 
     * @param e 
     */
    const divide = (s: number, e: number) => {
        if (e - s < 2) return;
        // 1. 从中间开始分割
        const half = (s + e) >> 1

        // 左边 [s, half)
        divide(s, half);

        // 右边  [half, e)
        divide(half, e)

        // 合并数组
        return merge(s, half, e)
    }

    divide(0, len)
}


